/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: yinsh
 * Date: 2025-02-19
 * Time: 17:37
 */
public class Test {
    //简单选择排序
    public void choiceSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[minIndex] > array[j]) {
                    minIndex = j;
                }
            }
            swap(array,minIndex,i);
        }
    }

    //插入排序
    public void insertSort (int[] array) {
        for (int i = 1; i < array.length; i++) {
            int tamp = array[i];
            int j = i-1;
            for (; j >= 0; j--) {
                if (array[j] > tamp) {
                    array[j+1] = array[j];
                }
                else {
                    break;
                }
            }
            array[j+1] = tamp;
        }
    }

    //希尔排序
    public void shellSort(int[] array) {
        int gap = array.length;
        while (gap > 1){
            gap = gap / 3 + 1;
            for (int i = gap; i < array.length; i++) {
                if (array[i] < array[i - gap]) {
                    swap(array,i,i-gap);
                }
            }
        }
    }

    //冒泡排序
    public void bubbleSort(int[] array) {
        for (int i = 0; i < array.length-1; i++) {
            boolean flag = false;
            for (int j = 0; j < array.length-i-1; j++) {
                if (array[j] > array[j+1]) {
                    swap(array,j,j+1);
                    flag = true;
                }
            }
            if (flag == false) {
                break;
            }
        }
    }

    //堆排序

    public void heapSort (int[] array) {
        int end = array.length-1;
        while (end > 0) {
            int tamp = array[0];
            array[0] = array[end];
            array[end] = tamp;
            siftDown(array, 0, end);
            end--;
        }
    }

    public void createHeap (int[] array) {
        int usedSize = array.length - 1;
        int parent = 0;
        for (; parent < array.length; parent++) {
            siftDown(array, parent, usedSize);
        }
    }


        private void siftDown (int[] array,int parent,int usedSize) {
        int child = parent*2+1;
        while (child < usedSize) {

            if (child+1<usedSize && array[child+1]<array[child]) {
                child++;
            }
            if (array[child] < array[parent]) {
                swap(array,child,parent);
            }else {
                break;
            }
            parent = child;
            child = parent*2+1;
        }
        }

    private void swap(int[] array,int x,int y) {
        int tamp = array[x];
        array[x] = array[y];
        array[y] = tamp;
    }
}
